from typing import List

# 方法一；行遍历，列遍历，每一个3*3遍历，时间复杂度O(n^2)
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        n = 9
        # 检验行
        for i in range(n):
            s = set()
            for j in range(n):
                if board[i][j] != '.' and board[i][j] in s:
                    return False
                s.add(board[i][j])
        # 检验列
        for j in range(n):
            s = set()
            for i in range(n):
                if board[i][j] != '.' and board[i][j] in s:
                    return False
                s.add(board[i][j])
        # 检验 3*3 小正方形
        for t in range(n):
            s = set()
            # x控制行，y控制列
            x = t // 3
            y = t % 3
            for i in range(x * 3, x * 3 + n//3):
                for j in range(y * 3, y * 3 + n//3):
                    if board[i][j] != '.' and board[i][j] in s:
                        return False
                    s.add(board[i][j])
        return True

# 方法二：同时检查行、列和宫格的唯一性，通过三种维度的集合检查，确保了数独的三个基本规则的验证。

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # 初始化行、列、宫的集合
        row = [set() for _ in range(9)]
        col = [set() for _ in range(9)]
        palace = [[set() for _ in range(3)] for _ in range(3)]
        # 双重循环遍历数独
        for i in range(9):
            for j in range(9):
                # 获取当前位置的数字
                num = board[i][j]
                # 跳过空格
                if num == ".":
                    continue
                # 重复数字检查
                if(num in row[i] or num in col[j] or num in palace[i//3][j//3]):
                    return False
                # 更新数字集合
                row[i].add(num)
                col[j].add(num)
                palace[i//3][j//3].add(num)
        return True
